package com.example.arithmeticleetcode.leetcode.dec;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2020-12-15 10:28
 **/
public class Demo12 {

    public int[] getSumAbsoluteDifferences(int[] nums) {
        int total = 0;
        int len = nums.length;
        for (int num : nums) {
            total += num;
        }
        int[] ret = new int[len];
        int stepSum = 0;
        int stepCount = -len;
        for (int i = 0; i < len; i++) {
            ret[i] = total - (stepSum << 1) + stepCount * nums[i];
            stepSum += nums[i];
            stepCount += 2;
        }
        return ret;
    }


    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return maxSubArray(nums, 0, nums.length);
    }

    private int maxSubArray(int[] nums, int begin, int end) {
        if (end - begin < 2) return nums[begin];
        int mid = (begin + end) >> 1;
        int leftSum = 0;
        int leftMax = Integer.MIN_VALUE;
        for (int i = mid - 1; i >= begin; i--) {
            leftSum += nums[i];
            leftMax = Math.max(leftMax, leftSum);
        }
        int rightSum = 0;
        int rightMax = Integer.MIN_VALUE;
        for (int i = mid; i < end; i++) {
            rightSum += nums[i];
            rightMax = Math.max(rightSum, rightMax);
        }
        return Math.max(leftMax + rightMax,
                Math.max(
                        maxSubArray(nums, begin, mid),
                        maxSubArray(nums, mid, end)
                        )
                );
    }

    public int maxSubArray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += nums[k];
                }
                maxValue = Math.max(sum, maxValue);
            }
        }
        return maxValue;
    }
}
